package com.lwx.algorithm.chapter6;

import com.lwx.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 用非递归的方法实现树的前序遍历
 */
public class Offer144 {
    public static void main(String[] args) {
        TreeNode t = new TreeNode(1, null, null);
        TreeNode t2 = new TreeNode(2, null, null);
        TreeNode root = new TreeNode(3, t, t2);
        Offer144 o = new Offer144();
        List<Integer> ret = o.preorderTraversal(root);
        System.out.println(ret);

    }

    /**
     * current 一直是树的左孩子，如果树的左孩子为空，那么从栈中弹出树节点，current使用树的右节点
     * current 指向当前节点，一直向左移动，元素入栈，直达current为空，才从栈中弹出元素的右子树为current
     * stack里的元素是为了是由他们的右子树
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null) {
            ret.add(current.getVal());
            stack.add(current);
            if (current.getLeft() != null) {
                current = current.getLeft();
            } else {
                if (!stack.isEmpty()) {
                    current = stack.pop().getRight();
                    // [3,1,2]这种情况
                    while (current == null && !stack.isEmpty()) {
                        current = stack.pop().getRight();
                    }
                }
            }
        }
        return ret;
    }
}
